The present invention relates to an arithmetic processor and, more particularly, to a high speed arithmetic processor and multiplier thereof which provides multiplication for internal arithmetic operations, and may be implemented by LSI.
A high speed binary multiplier utilizing a redundant binary adder tree is discussed on pages 683 to 690 of Trans. of IECE Japan, Vol. J66-D, No. 6 (1983). That multiplier utilizes a redundant binary expression (a kind of signed digit ("SD") expression) in which each digit is represented by an element of the set {-1, 0, 1}. In n-bit multiplication, n n-bit partial products, considered as redundant binary numbers, are added by partial trees in units of two in the redundant binary number system, and the product which is obtained as a redundant binary expression is converted to an ordinary binary expression. In the redundant binary number system, addition of two numbers without carry-propagation can be performed within a predetermined time irrespective of the number of digits to be added. Accordingly, a multiplier utilizing redundant binary adder trees is capable of executing n-bit multiplication at high speed in the computation time of log n. Computation speed is as high as that of a high speed multiplier utilizing Wallace trees, and is considerably higher than a prior art array multiplier. In addition, a regular array circuit structure is utilized, as in the case of an array multiplier, and with a simpler fan out arrangement than a multiplier using Wallace trees.
Use of the 2-bit Booth method reduces hardware requirements in the multiplier described above. In the 2-bit Booth method, the number of partial products may be reduced by almost half by recoding the multiplier in the quaternary signed digit number system, in which each digit is represented by an element of the set {-2, -1, 0, 1, 2}, which provides high speed operation and reduces the amount of hardware required. However, double folding of the multiplicand, which folding may be realized by left-shifting one bit, and inversion of positive and negative signs are necessary to generate a partial product. The inversion of positive and negative signs may be executed by obtaining a 2's complement binary number or by setting the "1" digits of the multiplicand to "-1" using the fact that inversion of positive and negative redundant binary numbers can be realized by inversion of the positive and negative signs of each digit.
Although the multiplier can easily generate a partial product, since each digit of the partial product may be positive (e.g., "1"), zero ("0") or negative (e.g., "-1"), it has been necessary to form all stages of the adder tree with the same ordinary redundant binary adder cells. No consideration, however, has been given to practical problems in the implementation of the multiplier, such as reducing the large number of elements (about 50 transistors) required, simplifying circuit structure in view of the large number of individual cells needed to form a redundant binary adder, and the difficulty in implementing the cells utilizing combinational circuitry since the number of elements required increases with the number of digits involved in the arithmetic operations which in turn requires complicated circuit structures.